As you begin using Borland C++, you'll probably want to learn how to use the container class libraries. In version 2.0, Borland supplied a container class library you could use for general data structures (if you derived the contained objects from the Object class). Beginning with version 3.0, Borland added a template-based container class library to help overcome some of the limitations of this Object-based library.
However, both these libraries define container classes and a number of iterator classes you can use to perform operations on the elements of a container object. Understanding how you can use these iterator classes will help you take advantage of the container classes in either library.
In this article, we'll look at some basic concepts behind
the design of a general iterator class and then create some simple
container and iterator classes of our own. In a future issue,
we'll show you how Borland implements these concepts in
its container libraries. To begin, let's consider the different
ways you might iterate the elements of an array or other data
structure.
In an ANSI C program, you'd typically create a global iterator function to handle iteration over the elements of an array. Usually, this type of function takes a pointer to a function as a parameter. (The qsort() standard library function works this way.) The iterator function will call this parameter function internally for each item in the array.
If the iterator function needs to call the parameter function with each element of the array, designing and calling the iterator function is relatively simple. However, if the iterator function will search for an element that matches a certain criterion, stop, and then resume from that point the next time you call the iterator function, you'll need to define a number of static variables for the function. The iterator function can then store a pointer to the array, the array's size, the number of matching elements in the array, the current index, or other information that doesn't change during iteration.
Unfortunately, you can't easily perform two or more iterations
at the same time (even on different arrays) when the iterator
function maintains this information in static variables. You can
work around this limitation by placing some of this information
in a structure and then passing that structure to the iterator
function each time you call it. (If this is beginning to sound
like an object-oriented design, you're thinking along the
correct lines.)
If you decide to move the project we just described to C++, you could incorporate the array into a class and redefine the iterator function as a member of the array's class. If you do this, a number of problems disappear, and some new opportunities arise.
For example, if the class's constructor and destructor handle all the memory allocation and deallocation for the array, you can add data members to the class to keep track of the array's size. With this information available to the iterator member function, you can easily avoid iterating past the end of the array.
In addition, each instance of the array's class can maintain its data independently of any other instance. However, if you want to perform two or more iterations simultaneously, you'll still need to maintain information that relates to the iteration process separately (current index, number of matching elements, and so on) and pass this data to the iterator member function.
If you move all the information that relates to the iteration process into its own class and move the iterator member functions from the array's class to this class as well, you've created an iterator class. In its most basic form, an iterator class is a companion class to a type of data structure in which the iterator encapsulates the data and behavior necessary for iteration. If you think of a simple array as a container, you can think of an object of an iterator class as an intelligent index into the array.
The primary reason for creating and using iterator classes is to remove from the container class data and member functions that don't really relate to containing the data. By keeping the division of responsibility clear, the code will be easier to maintain and more flexible to use.
For instance, in a situation in which you might create two container classes, you may instead be able to create a single container class and two very simple iterator classes. If you keep the code that relates to containing the data separate from the code that relates to iterating the elements of the container, you'll be able to perform different types of iterations on the same container instead of creating two different types of container objects with the same data.
When you define an iterator class, you'll typically include
the following: an initializing member function (usually a constructor),
an iterating member function, and a member function that resets
the iteration process. There are other features you can add to
an iterator class, but these are the most basic. Now, let's
create a simple program that defines an array class and two iterator
classes.
To begin, launch the Borland C++ version 3.1 Integrated Development Environment (IDE) for DOS. (This example will also work as an EasyWin application if you want to use the 3.1 or 4.0 IDE for Windows.)
When the IDE's desktop and menu bar appear, choose New from the File menu to open a source file editor window. When the new editor window appears, enter the program from Listing A.
When you finish entering the code, choose Save from the File menu and enter ITERATOR.CPP in the Save File As entry field. Click OK to save the file.
Next, choose Application... from the Options menu. In
the Set Application Options dialog box, click DOS Standard and
then click OK.
The ITERATOR.CPP file defines three classes: an array of integers
(intArray), a class that defines objects that iterate
from the beginning of an intArray object's array
to the end (forwardIterator), and a class that iterates
in the other direction (reverseIterator). Let's
look at each class individually.
The intArray class is probably the most basic implementation
of a dynamically allocated array of integers. Its constructor
allocates the memory for the array (data) and then sets
the data member max with the array's size.
The forwardIterator class defines four data members that describe the current iteration process. The class uses the first three data members (currentIndex, beg, and end) to keep the iterator from trying to access locations outside the boundaries of the array.
The fourth data member, myArray, maintains a reference to the companion intArray object. We made this member a reference because it doesn't make sense to create an object of this class if there isn't already an intArray object to initialize this member. (Remember, you must initialize any reference in C++.)
In addition to the data members, the forwardIterator class defines one private member function, two constructors, and two public member functions. The private member function advanceIndex() allows us to customize the iteration direction. In this class, advanceIndex() returns the currentIndex data member and then increments it.
The forwardIterator class's first constructor sets the values of the four data members. The second constructor defines a conversion from an object of this class to an integer value. If the value of the currentIndex data member is within the bounds of the array's size, the integer conversion constructor returns 1; if not, it returns 0. Writing this type of conversion constructor allows us to place a forwardIterator object identifier in a statement that expects an integerwhile() or if()to test the state of the iterator.
The reset() member function returns forwardIterator to its initial state. You'll call this function when you need to begin the iteration again.
At the end of the forwardIterator class, we overload
the function call operatoroperator ()to
provide a simple syntax for iterating the corresponding array.
(If you aren't familiar with doing this, see C++ Language Basics - Overloading the function call operator.) This operator returns
a reference to the element of the array at the position currentIndex.
Returning a reference to the elements of the array mimics the
behavior of a traditional array.
The reverseIterator class inherits publicly from the forwardIterator class. This means that a reverseIterator object has the same data members and inherits the reset() and function call operator definitions from the forwardIterator class.
The reverseIterator class redefines the private member function advanceIndex() to reverse the iteration direction that the forwardIterator class defines. Since the integer conversion constructor from the forwardIterator class tests for an out-of-bounds index in the opposite direction, we supply an integer conversion constructor for the reverseIterator class as well.
By the way, if you combine these two tests in the forwardIterator
class's conversion constructor, the compiler won't
be able to convert a reverseIterator object to an integer.
A C++ compiler won't convert a derived class like reverseIterator
to a base class like forwardIterator in order to perform
this type of conversion.
In the main() function, we create an intArray object with ten elements and then create a forwardIterator object and a reverseIterator object to iterate over the array. Next, we use the forwardIterator object to initialize each element of the array.
Before using the forwardIterator object again, we call
its reset() member function to reset its currentIndex
data member to access the first element of the array. Finally,
we use a while() loop that displays the values from each
iterator until one of them reaches the end of the array.
To build the program, choose Make from the Compile menu. After the IDE builds the executable file, the Compiling status dialog box will display a message that indicates a successful build.
Now, choose Quit from the File menu to exit the IDE. At the DOS
prompt, enter ITERATOR. When the program runs, you'll
see the output shown in Figure A.
Figure A - The iterator classes from ITERATOR.EXE allow you to iterate an array forward or backward.
0 18 2 16 4 14 6 12 8 10 10 8 12 6 14 4 16 2 18 0
Iterator classes provide a nice compromise between the flexibility
of global iterator functions and the power of class-member iterating
functions. Next month, we'll show you how Borland implements
these and other iterator class design techniques in its container
class libraries.
Copyright (c) 1996 The Cobb Group, a division of Ziff-Davis Publishing Company. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of Ziff-Davis Publishing Company is prohibited. The Cobb Group and The Cobb Group logo are trademarks of Ziff-Davis Publishing Company.